1527D - MEX Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[2 * N + 5];
int cnt, headers[N + 5];
void add(int from, int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int father[N + 5];
long long siz[N + 5];
bool vis[N + 5];
void dfs(int place, int fa)
{
    siz[place]++;
    father[place] = fa;
    for (int i = headers[place]; i; i = que[i].next)
        if (que[i].to != fa)
        {
            dfs(que[i].to, place);
            siz[place] += siz[que[i].to];
        }
}
long long ans[N + 5];
int main()
{
    int n, t, u, v;
    scanf("%d", &t);
    while(t--)
    {
        int jump = 0;
        scanf("%d", &n);
        for (int i = 1; i < n;i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dfs(0, 0);
        for (int i = headers[0]; i; i = que[i].next)
            ans[0] += siz[que[i].to] * (siz[que[i].to] - 1) / 2;
        int l = 0, r = 1, place = 1;
        vis[1] = 1;
        while(father[place])
        {
            vis[father[place]] = 1;
            place = father[place];
        }
        siz[0] -= siz[place];
        vis[0] = 1;
        ans[2] = siz[0] * siz[1];
        ans[1] = (long long)n * (n - 1) / 2 - ans[0] - ans[2];
        bool flag = 1;
        for (int i = 2; i < n;i++)
        {
            if(vis[i])
                ans[i + 1] = siz[l] * siz[r];
            else
            {
                int place = i;
                while(place && !vis[place])
                {
                    jump++;
                    if(place==father[place])
                        break;
                    vis[place] = 1;
                    place = father[place];
                }
                if (place != l && place != r)
                {
                    flag = 0;
                    break;
                }
                else
                {
                    if(place==l)
                        l = i;
                    else
                        r = i;
                    ans[i + 1] = siz[l] * siz[r];
                }
            }
        }
        for (int i = 2; i < n; i++)
            ans[i] -= ans[i + 1];
        for (int i = 0; i <= n;i++)
            printf("%lld ", ans[i]);
        printf("\n");
        for (int i = 0; i <= n; i++)
        {
            ans[i] = 0;
            headers[i] = siz[i] = father[i] = 0;
            vis[i] = 0;
        }
        cnt = 0;
    }
    return 0;
}